package mybtree;

public class Btree {

    public static final int M = 3;
    public Node root;

    static class Node {
        public int[] keys;//关键字
        public Node[] subs;//孩子结点
        public Node parent;//双亲结点
        public int usedSize;//使用的空间个数

        public Node() {
            //多分配一个空间是为了后面便于我们分裂结点
            this.keys = new int[M];
            this.subs = new Node[M+1];
        }
    }

    //插入
    public void insert(int key) {
        //根节点为空，直接插入
        if(root == null) {
            root = new Node();
            root.keys[0] = key;
            root.usedSize = 1;
            return;
        }

        //先查找是否存在key
        Pair<Node,Integer> find = find(key);

        //如果已经存在，直接返回
        if(find.getVal() != -1) {
            return;
        }

        //不存在，需要进行插入
        Node cur = find.getKey();
        //插入是在叶子结点进行的，不需要调整孩子结点
        int i = cur.usedSize - 1;
        for (; i >= 0; i--) {
            if(cur.keys[i] > key) {
                cur.keys[i+1] = cur.keys[i];
            } else {
                break;
            }
        }
        cur.keys[i+1] = key;
        cur.usedSize++;

        //是否需要进行分裂
        if(cur.usedSize == M) {
            split(cur);
        }
    }

    private void split(Node cur) {
        Node newNode = new Node();
        Node parent = cur.parent;

        //进行keys和孩子结点的拷贝
        int mid = M / 2;
        int i = 0;
        int j = mid + 1;
        for(; j < cur.usedSize; j++) {
            newNode.keys[i] = cur.keys[j];
            newNode.subs[i] = cur.subs[j];
            //如果拷贝过来的孩子结点不为空，需要修改孩子结点的双亲结点
            if(newNode.subs[i] != null) {
                newNode.subs[i].parent = newNode;
            }
            //usedSize 随之修改
            newNode.usedSize++;
            i++;
        }

        //还差一个孩子结点没有拷贝，再次拷贝孩子结点
        newNode.subs[i] = cur.subs[j];
        if(newNode.subs[i] != null) {
            newNode.subs[i].parent = newNode;
        }

        //新结点的双亲结点设置为 parent
        newNode.parent = parent;

        //设置 cur 的 usedSize 数值
        cur.usedSize = mid;

        //需要提取的中间关键字
        int midVal = cur.keys[mid];

        //特殊情况：当分裂的结点正好是根结点
        if(cur == root) {
            root = new Node();
            root.keys[0] = midVal;
            root.subs[0] = cur;
            root.subs[1] = newNode;
            cur.parent = newNode.parent = root;
            root.usedSize = 1;
            return;
        }

        //处理 parent 结点
        //将 cur 的中间关键值提到 parent;
        int end = parent.usedSize - 1;
        for(; end >= 0; end--) {
            if(parent.keys[end] > midVal) {
                parent.keys[end+1] = parent.keys[end];
                parent.subs[end+2] = parent.subs[end+1];
            } else {
                break;
            }
        }
        parent.keys[end+1] = midVal;
        parent.subs[end+2] = newNode;
        parent.usedSize++;

        //是否需要继续分裂
        if(parent.usedSize == M) {
            split(parent);
        }
    }

    //查找
    public Pair<Node,Integer> find(int key) {
        Node cur = root;
        Node prev = null;
        while(cur != null) {
            int i = 0;
            while(i < cur.usedSize) {
                if(cur.keys[i] == key) {
                    //存在该节点
                    return new Pair<>(cur,i);
                } else if(cur.keys[i] > key) {
                    //需要进入孩子结点继续查找
                    break;
                } else {
                    //继续查找
                    i++;
                }
            }
            prev = cur;
            cur = cur.subs[i];
        }

        //找不到，返回双亲结点
        return new Pair<>(prev,-1);
    }

    public void inorder(Node root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.usedSize]);
    }
}
